#include <iostream>
using namespace std;

typedef int ElemType;
/*数据结构定义*/
typedef struct LinkedNode{
    int data;
    struct LinkedNode *next;
}LinkedNode,*LinkedList;

void soutCn(char chinese[]);
void soutNum(int num);
void printLinkedList(LinkedList list,int tag);

/*构建带头节点循环单链表*/
/*算法思想(尾插法)：
 *              1.构建一个不存数据的头结点，且指针域指向自己形成循环；
 *              2.定义一个尾指针，用于尾插；
 *              3.初始化插入节点，并从尾指针处插入链表；
 *          注意：由于在初始化时已经将头结点形成了循环，所以在插入的时候不需要再操作；*/
void create(LinkedList &list,ElemType data[],int len){
    //新建头结点
    list = (LinkedNode *)malloc(sizeof(LinkedNode));
    list->next = list;
    //设置尾指针，进行尾插法
    LinkedNode *tail = list;
    //插入节点
    for(int i=0;i<len;i++){
        //初始化一个新节点
        LinkedNode *newNode = (LinkedNode *) malloc(sizeof(LinkedNode));
        newNode->data = data[i];
        newNode->next = NULL;
        //插入
        newNode->next = tail->next;
        tail->next = newNode;
        //移动尾指针
        tail = tail->next;
    }
}

//头插法
/*算法思想（头插法）：
 *                和尾插法差不多，但是不用设置尾指针；
 *                循环的也是在头结点初始化的时候生成；*/
void createWithHeadInsert(LinkedList &list,ElemType data[],int len){
    //初始化头结点
    list = (LinkedNode *) malloc(sizeof(LinkedNode));
    list->next = list;
    //插入节点
    for (int i = 0; i < len; ++i) {
        //出初始化新节点
        LinkedNode *newNode = (LinkedNode *) malloc(sizeof(LinkedNode));
        newNode->data = data[i];
        newNode->next = NULL;
        //插入新节点
        newNode->next = list->next;
        list->next = newNode;
    }
}

/*设计一个算法，将一个带头结点的循环单链表中所有结点的链接方向逆转*/
/*算法思想：
 *       1.将链表拆成头结点和数据链；
 *       2.再将数据链的节点拆下来依次头插入头结点，构造逆置；
 *   注意：这种从一条链拆下节点的操作一定要事先保存下一个节点，防止断链*/
//逆置：首先想到头插法
void reverse(LinkedList &list){
    //分成数据链和头结点
    LinkedNode *pNode = list->next;
    list->next = list;
    //依次进行头插法进行逆置
    /*注意注意：循环链表遍历的跳出条件*/
    while(pNode != list){
        //备份下一个节点，防止断链
        LinkedNode *tmp = pNode->next;
        //插入
        pNode->next = list->next;
        list->next = pNode;
        //判定插入的是尾节点
        if (list->next == list){
            pNode->next = list;
        }
        //移动指针，插入下一个数据节点
        pNode = tmp;
    }
}

/*设计一个算法将循环单链表左移k个结点。*/
/*算法思想：对于循环链表，左移动k位后，循环链表中第+1个结点将会称为链表中第一个数据结点，
 *         所以只需将头指针指向第k+1个结点，就能实现左移k的操作。*/
/*      注意注意：如果题目没说有没有头结点，自行选择即可，
 *               本题不带头结点显然方便，所以算法设计成不带头结点的，
 *               而且要在算法注释中写出来告诉改卷老头。*/
void leftMove(LinkedList &list,int k){
    for (int i = 0; i < k; ++i) {
        list = list->next;
    }
}

/*设计算法将不带头结点的循环单链表中节点的直接前驱删除。*/
/*算法思想：
 *       利用循环链表的性质，从当前节点下一个出发，
 *       设置preNode和curNode，一直往后遍历（绕一圈），
 *       直到cur->next为当前节点,删除curNode*/
void deletePreNode(LinkedNode *node){
     LinkedNode *preNode = node;
     LinkedNode *curNode = node->next;
     while(curNode->next != node){
         preNode = curNode;
         curNode = curNode->next;
     }
     //此时cur为待删除节点，pre为其前驱
     //删除
     preNode->next = curNode->next;
     free(curNode);
}

/*已知L为一个单链表的头结点，设计算法将表中从1号结点到m号结点构成一个逆置的循环链表。*/
/*算法思想：找到i和m节点前驱（绕圈），将中间这段取下来逆置（头插法实现）*/
LinkedNode *getPre(int i,LinkedList list);
LinkedNode *compose(LinkedList list,int i,int m){
    //获取目标子链两端的前驱
    LinkedNode *iPre = getPre(i,list);
    LinkedNode *mPre = getPre(m,list);
    //取下来，注意备份
    LinkedNode *curNode = iPre->next;//取下子链
    iPre->next = mPre->next->next;//断开
    mPre->next->next = NULL;
    //逆置插入（头插）
    LinkedList reverseList = (LinkedNode *) malloc(sizeof(LinkedNode));
    reverseList->next = reverseList;//这里就可以保证头插自动产生循环
    while(curNode){
        /*熟练使用头插三步走*/
        LinkedNode *tmp = curNode->next;//1.备份
        curNode->next = reverseList->next;//2.插入
        reverseList->next = curNode;
        curNode = tmp;//3.下一个
    }
    return reverseList;
}
LinkedNode *getPre(int i,LinkedList list){
    int count = 0;
    LinkedNode *curNode = list->next;
    LinkedNode *preNode = list;
    while(curNode){
        if (++count == i)
            return preNode;
        preNode = curNode;
        curNode = curNode->next;
    }
    return NULL;
}

/*已知La和Lb分别为两个循环单链表的头节点指针，m和n分别为La和Lb中数据节点的个数，设计时间复杂度最小的
算法将两个链表合并成一个带头的循环单链表。*/
/*算法思想：由于需要设计时间复杂度最小的算法，所以采用遍历较短的链表，将其中的节点一个个的插入到长链中去*/
LinkedNode * merge(LinkedList la,int m,LinkedList lb,int n){
    //找到长短链
    LinkedList longList = m>n?la:lb;
    LinkedList shortList = m<n?la:lb;
    //插入节点
    LinkedNode *pNode = shortList->next;
    while(pNode != shortList){
        //保存下一个节点
        LinkedNode *tmp = pNode->next;
        //插入长链
        pNode->next = longList->next;
        longList->next = pNode;
        //遍历下一个短链节点
        pNode = tmp;
    }
    //删除短链
    shortList = NULL;
    la = NULL;
    lb = NULL;
    return longList;
}

//打印
void soutCn(char chinese[]){
    printf("%s", chinese);
}
void soutNum(int num){
    printf("%d", num);
}
void shift(){
    printf("\n");
}
void printLinkedList(LinkedList list,int tag){
    //1是带头节点，0是不带头结点
    LinkedNode *p = tag?list->next:list;
    /*循环链表的遍历终止条件*/
    do {
        printf("%d ",p->data);
        p = p->next;
    } while (p != list);
    shift();
}
int main(){
    int data[] = {1,2,3,4,5,6,7,8,9,10};
    int len = sizeof(data)/sizeof(data[0]);
    LinkedList list;
//    create(list,data,len);
    createWithHeadInsert(list,data,len);
    reverse(list);
//    /*假装没有头结点*/
//    list->data = 0;
//    leftMove(list,3);
//    deletePreNode(list->next->next->next);
//    printLinkedList(list,0);
//    printLinkedList(list,1);
//    LinkedList reList = compose(list,2,5);
//    printLinkedList(reList,1);
    int data2[] = {11,12,13};
    LinkedList list2;
    create(list2,data2,3);
    list = merge(list,10,list2,3);
    printLinkedList(list,1);

    return 0;
}